package 树.middle;

import java.util.Stack;

/**
 * @author Lw中
 * @date 2021/7/22 23:17
 */
public class JiuShiBa {

    // 98.验证二叉搜索树
    // 初始化二叉树节点
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

    // 方法一：使用中序遍历，判断数组是否为升序
    public boolean isValidBST(TreeNode root) {
        // 创建栈用于存储节点
        Stack<TreeNode> stack = new Stack<>();
        //用于存储当前节点的前继节点
        double inorder = -Double.MAX_VALUE;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }

}
